Задача двух генералов

Задача двух генералов — в вычислительной технике мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадёжному каналу связи. Эта задача часто рассматривается в рамках курса компьютерных сетей (в частности протокола TCP), хотя применима и к другим средствам связи. В литературе также иногда упоминается как задача двух армий.

Определение

Две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагеря этих армий располагаются на двух холмах, разделённых долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, генералы заранее (пока была связь) приняли принципиальное решение о штурме, но не согласовали точное время штурма (время Ч).

Для успешного штурма генералы должны атаковать город одновременно. Штурм, предпринятый только одной армией, приведёт к катастрофическим последствиям для атакующих. Требуется найти алгоритм обмена сообщениями, после которого каждый генерал был бы уверен, что они оба атакуют в указанное время.

Отметим, что достичь такого соглашения (в случае надёжного канала связи) очень просто — достаточно одного сообщения с временем начала штурма и одного сообщения, подтверждающего согласие. Сложность задачи заключается в невозможности разработать алгоритм гарантированного обмена этими сообщениями.

Иллюстрация проблемы

Предположим, первый генерал отправляет второму сообщение «Атакуем завтра в девять часов утра». Отправив посыльного, первый генерал не знает, добрался ли посыльный до второго генерала. Не зная, поддержит ли второй генерал его действия, первый может отложить штурм. Зная это, второй генерал может отправить подтверждающее сообщение «Я получил Ваше сообщение и атакую завтра в девять часов утра». Но это сообщение также может быть перехвачено противником. Зная, что первый генерал не начнёт штурм без подтверждения, второй генерал также может отложить атаку. Первый генерал может отправить сообщение «Я получил Ваше подтверждение о времени начала штурма», но оно также может быть перехвачено. Быстро становится очевидным, что, сколько бы ни было циклов обмена сообщениями, нет способа гарантированно уведомить обоих генералов о том, что их сообщения получены. Таким образом, задача не имеет решения.

Доказательство

Предположим, что есть некоторая последовательность сообщений, доставленных или перехваченных, которая позволяет обоим генералам гарантированно согласовать время начала штурма. В таком случае существует некоторое минимальное подмножество таких сообщений. Рассмотрим последнее сообщение в этой минимальной последовательности. Так же, как и любое другое сообщение, оно может быть перехвачено. Если оно не будет доставлено, то условие согласованности действий не выполнится, и один из генералов (вероятнее всего, получатель) отложит свою атаку. С точки зрения другого генерала, алгоритм обмена будет соблюден, и он начнет штурм в полной уверенности, что будет поддержан. Таким образом, при использовании заведомо правильного алгоритма, создается ситуация, в которой один генерал штурмует город, а другой — нет. Это противоречит нашему допущению о существовании алгоритма решения задачи.

Инженерные подходы

Прагматичный подход к решению задачи предполагает не полное устранение ненадёжности канала, а её сведение к допустимому уровню. Например, первый генерал может отправить сразу 100 посыльных с сообщением, считая, что вероятность перехвата сразу всех посыльных чрезвычайно низка, и затем, не дожидаясь подтверждения, атаковать в указанное время. Однако такой способ, конечно же, не обеспечивает строгой гарантии согласованности действий генералов.

История

Задача двух генералов и доказательство нерешаемости были впервые опубликованы Э.А. Аккоюнлу, К. Эканадхамом и Р.В. Хубером в 1975 г. в «Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций», где она описана, начиная со страницы 73 в контексте общения между двумя группами гангстеров.

См. также

• Задача византийских генералов